package leetcode

// https://leetcode.com/problems/car-pooling/
type Problem string

// diff array algorithm, detail:
// https://labuladong.gitee.io/algo/2/20/25/
type Difference struct {
	diff []int
}

// Constructor a new Difference Object.
func Constructor(array []int) Difference {
	if len(array) < 1 {
		panic("array empty")
	}
	diff := make([]int, len(array))
	diff[0] = array[0]
	for i := 1; i < len(array); i++ {
		diff[i] = array[i] - array[i-1]
	}
	return Difference{diff: diff}
}

// Increment diff array add certainly value 'val' from indices i to j.
func (d *Difference) Increment(i, j, val int) {
	d.diff[i] += val
	if j+1 < len(d.diff) {
		d.diff[j+1] -= val
	}
}

// Result return the result array after a series of operations.
func (d *Difference) Result() []int {
	res := make([]int, len(d.diff))
	res[0] = d.diff[0]
	for i := 1; i < len(d.diff); i++ {
		res[i] = d.diff[i] + res[i-1]
	}
	return res
}

// CarPoolingByClass resolve by pre-define class.
func CarPoolingByClass(trips [][]int, capacity int) bool {
	diff := make([]int, 1001)
	df := Constructor(diff)
	for _, trip := range trips {
		i, j, val := trip[1], trip[2]-1, trip[0]
		df.Increment(i, j, val)
	}
	ed := df.Result()
	for _, e := range ed {
		if e > capacity {
			return false
		}
	}
	return true
}

// resolve by embed.
// Input: trips = [[2,1,5],[3,3,7]], capacity = 4.
// Output: false.
// 0 <= fromi < toi <= 1000.
func carPooling(trips [][]int, capacity int) bool {
	diff := make([]int, 1001)
	for _, trip := range trips {
		i, j, value := trip[1], trip[2]-1, trip[0]
		diff[i] += value
		if j+1 < len(diff) {
			diff[j+1] = diff[j+1] - value
		}
	}
	// get result
	res := make([]int, 1001)
	res[0] = diff[0]
	for i := 1; i < len(diff); i++ {
		res[i] = res[i-1] + diff[i]
	}
	// verify each value less than capacity
	for _, v := range res {
		if v > capacity {
			return false
		}
	}
	return true
}
